Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS110 Intro to Computing / 2015-Spring / Lectures

1. Genetic Algorithm

The Genetic Algorithm (GA) is a computing technique based on Darwinian evolution. To use this, you start with a population of random guesses, rank them based on some fitness score, make small adjustments over time, and select the best at each generation. Over time, you can evolve anything, given that it can have a score associated with it.

In this experiment, we will evolve a picture of Taylor Swift. That is, we will evolve (using simulated selection, mutation, and mating) a program that can generate a picture of Taylor Swift. Why? This is largely an example of using arrays, and to show that computers can find unique solutions to problems.

Table of Contents

• 1. Genetic Algorithm
  • 1.1 "Information"
  • 1.2 Genotype
  • 1.3 Fitness
  • 1.4 Evolve
  • 1.5 Results

1.1 "Information"

Creating this kind of representation of an image could also be practical. For example, a 100 x 100 pixel image contains 100 x 100 x 4 x 8 (320,000) bits of information. If we could reduce that to 50 x 7 x 8 (2,800) bits of information, that would be quite a savings (0.8 % of the original size).

For this experiment, we will need a target image. Here is an image that is 100 pixels by 100 pixels:

%download http://www.avatarsdb.com/avatars/taylor_swift.jpg

Downloaded 'taylor_swift.jpg'.

We will attempt to evolve this image.

1.2 Genotype

The genotype will be composed of 50 random circles of a particular color (including red, green, blue, and alpha components) and a particular radius, at a given x,y location. So each genotype is made up of 50 of these:

• red
• green
• blue
• alpha
• radius
• x
• y

So, a genotype is 50 x 7, or 350 numbers. Each value will be represented by a number between 0 and 1, and will be scaled appropriately for its use. Every 7 values (gene) will be used to draw one circle.

We draw each of the 50 circles to get an image like the following. Here we will draw the image that the genotype represents (the phenotype) on a PGraphics object, and then at the end render it to the Sketch.

Note that to use a PGraphics object, we call createGraphics() with width and height as arguments. Then, we call pg.fill(), pg.noStroke(), and pg.ellipse(). These are just like fill(), noStroke(), and ellipse() but they work on the PGraphics object, rather than on the canvas.

At some point later, we call image(pg, 0, 0) which says to make an image out of the PGraphics object, and draw it at (0, 0).

// Create the space for the full gene:
float [] gene = new float[350];

// Set each location to a number between 0 and 1:
for (int i = 0; i < 350; i++) {
    gene[i] = random();
}

// Create a place to draw the creature (the Phenotype):
PGraphics pg = createGraphics(100, 100);

// Now we draw it:
for (int i = 0; i < 350; i += 7) {
    r = gene[i + 0] * 255;
    g = gene[i + 1] * 255;
    b = gene[i + 2] * 255;
    a = gene[i + 3] * 255;
    radius = gene[i + 4] * 100/2;
    x = gene[i + 5] * 100;
    y = gene[i + 6] * 100;
    pg.fill(r, g, b, a);
    pg.noStroke();
    pg.ellipse(x, y, radius, radius);
}
// Finally, show the creature:
image(pg, 0, 0);

Sketch #30:

Run Pause setup() draw()

Sketch #30 state: Loading...

That doesn't look very much like Taylor Swift. How off is it?

1.3 Fitness

We give a phenotype a fitness value by comparing each pixel of the generated image with our target image. To compare two pixels, we sum the difference of each red, green, blue, and alpha components.

PImage target = loadImage("taylor_swift.jpg");
target.loadPixels();

// Create a place to draw the creature (the Phenotype):
PGraphics pg = createGraphics(100, 100);


int computeFitness(pg, target) {
    gdata = pg.toImageData().data; // height, width, data
    tdata = target.imageData.data;
    fit = 0;
    for (int i = 0; i < (100 * 100 * 4); i++) {
        fit += abs(gdata[i] - tdata[i]);
    }
    return 100 * 100 * 4 * 255 - fit;
}

void setup() {
    // Create the space for the full gene:
    float [] gene = new float[350];

    // Set each location to a number between 0 and 1:
    for (int i = 0; i < 350; i++) {
        gene[i] = random();
    }

    // Now we render it:
    for (int i = 0; i < 350; i += 7) {
        r = gene[i + 0] * 255;
        g = gene[i + 1] * 255;
        b = gene[i + 2] * 255;
        a = gene[i + 3] * 255;
        radius = gene[i + 4] * 100/2;
        x = gene[i + 5] * 100;
        y = gene[i + 6] * 100;
        pg.fill(r, g, b, a);
        pg.noStroke();
        pg.ellipse(x, y, radius, radius);
    }
}

void draw() {
    // Finally, show the creature:
    image(pg, 0, 0); 

    // and compute its fitness with the target image:
    fitness = computeFitness(pg, target);

    fill(0);
    text(fitness, 1, 100 + 1); 
    fill(255);
    text(fitness, 0, 100); 
    noLoop();
}

Sketch #29:

Run Pause setup() draw()

Sketch #29 state: Loading...

(Note how I made the number show... I display it once in black, offset by +1, +1, and then again in white.

In an example I just ran, the result was 7,195,509. This is a low score. The best score is 100 x 100 x 4 x 255:

%%python
print(100 * 100 * 4 * 255)

10200000

So, the best score is 10,200,000, if we match every pixel exactly.

1.4 Evolve

To evolve a picture, we'll follow this algorithm:

1. generate a random population of 25 genotypes
2. compute their fitness (difference between phenotype and target image)
3. sort the population by fitness (lower fitness means less differences)
4. mutate some of the genes
5. combine some of them together (crossover)
6. go to step 2

I will have a couple of variables that don't every change. I will write these in uppercase by convention to indicate the fact that they are constants.

In this demonstration, I need to have an array of geneotypes. But wait, the geneotype is an array! That is right: I need an array of arrays. That is written like:

float [][] pop = new float[POPSIZE][GENESIZE];

To make this work, I need to be able to sort the population based on fitness. this will turn out to be a very important function in computer science. I've done the sorting in a very simple way. We will return to this issue later.

int POPSIZE = 25;
int GENESIZE = 50 * (4 + 2 + 1); // 4 for color, 2 for xy, 1 for radius

PImage target = loadImage("taylor_swift.jpg");
target.loadPixels();

float [][] pop = new float[POPSIZE][GENESIZE];
float [] fitness = new float[POPSIZE];
PGraphics [] pgraphics = new PGraphics[POPSIZE];

float[] makeGene() {
    float[] gene = new float[GENESIZE];
    for (int i = 0; i < GENESIZE; i++) {
        gene[i] = random(.999999);
    }
    return gene;
}

float[] copyGene(int pos) {
    float[] gene = new float[GENESIZE];
    for (int i = 0; i < GENESIZE; i++) {
        gene[i] = pop[pos][i];
    }
    return gene;
}

void setup() {
    // Create the population:
    size(500, 500);
    for (int i = 0; i < POPSIZE; i++) {
        pop[i] = makeGene();
        pgraphics[i] = createGraphics(100, 100);
    }
}

PGraphics createPhenotype(int gene_pos, int w, int h) {
    pg = pgraphics[gene_pos];
    pg.background(255);
    for (int i = 0; i < GENESIZE; i += 7) {
        r = pop[gene_pos][i + 0] * 255;
        g = pop[gene_pos][i + 1] * 255;
        b = pop[gene_pos][i + 2] * 255;
        a = pop[gene_pos][i + 3] * 255;
        radius = pop[gene_pos][i + 4] * w/2;
        x = pop[gene_pos][i + 5] * w;
        y = pop[gene_pos][i + 6] * h;
        pg.fill(r, g, b, a);
        pg.noStroke();
        pg.ellipse(x, y, radius, radius);
    }
    return pg;
}

void drawPopulation() {
    gene = 0;
    for (j=0; j < 5; j++) {
        for (i=0; i < 5; i++) {
            pg = createPhenotype(gene, 100, 100);
            image(pg, i * 100, j * 100); 
            fill(0);
            text(fitness[gene], i * 100 + 1, j * 100 + 100 + 1); 
            fill(255);
            text(fitness[gene], i * 100, j * 100 + 100); 
            gene++;
        }
    }
}

void sortPopulation() {
    for (int i = 0; i < POPSIZE - 1; i++) {
        for (int j = i + 1; j < POPSIZE; j++) {
            if (fitness[i] < fitness[j]) { // swap
                temp_fitness = fitness[i];
                fitness[i] = fitness[j];
                fitness[j] = temp_fitness;
                // swap genes:
                for (int c = 0; c < GENESIZE; c++) {
                    temp = pop[i][c];
                    pop[i][c] = pop[j][c];
                    pop[j][c] = temp;
                }
            }
        }
    }
}

int computeFitness(int gene) {
    pg = createPhenotype(gene, 100, 100);
    gdata = pg.toImageData().data; // height, width, data
    tdata = target.imageData.data;
    fit = 0;
    for (int i = 0; i < (100 * 100 * 4); i++) {
        fit += abs(gdata[i] - tdata[i]);
    }
    return 100 * 100 * 4 * 255 - fit;
}

void mutatePopulation(percent) {
    for (int p = 1; p < POPSIZE; p++) {
        for (int i = 0; i < GENESIZE; i++) {
            if (random(1) < percent) 
                pop[p][i] = random(0, .99999);
        }
    }
}

int fitnessSum() {
    sum = 0;
    for (int i = 0; i < POPSIZE; i++) {
        sum += fitness[0];
    }
    return sum;
}

int select() {
    index = 0;
    partsum = 0.0;
    sumFitness = fitnessSum();
    spin = random() * sumFitness;
    while (index < POPSIZE - 1) {
        partsum += fitness[index];
        if (partsum >= spin) {
            break;
        }
        index += 1;
    }
    return index;
}


void crossoverPopulation(percent) {
    for (int p = POPSIZE - 1; p > POPSIZE - (POPSIZE * percent); p--) {
        c1 = select();
        c2 = select();
        crossover_point = random(GENESIZE);
        for (int i = 0; i < GENESIZE; i++) {
            if (i < crossover_point) 
                pop[p][i] = pop[c1][i];
            else
                pop[p][i] = pop[c2][i];
        }
    }
}

void draw() {
    for (int p = 0; p < POPSIZE; p++) {
        fitness[p] = computeFitness(p);
    }
    sortPopulation();
    drawPopulation();
    mutatePopulation(.01);
    crossoverPopulation(.80);
}

Sketch #31:

Run Pause setup() draw()

Sketch #31 state: Loading...

1.5 Results

Settings:

Parameter	Value
Circles used	50
Population Size	25
Mutation Rate	0.01
Replacements from Selection	0.80
Crossover Points	1

Resulting evolved images:

Original/target	1 Hour	2 Hours	10 Hours